package com.jacklei.ch01;

public class 路径权值最大 {

    public static void main(String[] args) {
        Node root = new Node(1);
         root.left = new Node(2);
         root.right = new Node(3);
         root.left.left = new Node(4);
         root.left.right = new Node(5);
         root.right.left = new Node(6);
         root.right.right = new Node(7);
        System.out.println(maxPath(root));
    }

    public static class Node{
        int value;
        Node left;
        Node right;

        public Node(int value) {
            this.value = value;
        }
    }

    public static int maxPath(Node node){
        if(node.left == null && node.right == null)
            return node.value;
        int result = 0;
        if(node.left != null){
            result = maxPath(node.left);
        }
        if(node.right != null){
            result = Math.max(result, maxPath(node.right));
        }
        return result + node.value;
    }
}
